|
|
Generating random pattern-avoiding matrices
Kučera, Stanislav ; Jelínek, Vít (vedoucí práce) ; Šámal, Robert (oponent)
Binární matice neobsahující menší matici jako podmatici se stávají zajímavým tématem. V mé práci uvádím dva nové algoritmy pro testování, zda velká čtvercová binární matice obsahuje menší binární matici, a randomizovaný proces, který aproximuje uniformní náhodnou matici neobsahující danou matici. Toto umožní vědeckým pracovníkům testovat jejich hypotézy na náhodných maticích. Proto moje práce také obsahuje efektivní přenositelnou implementaci všech zmíněných algoritmů. Powered by TCPDF (www.tcpdf.org)
|
|
|
Generating random pattern-avoiding matrices
Kučera, Stanislav ; Jelínek, Vít (vedoucí práce) ; Šámal, Robert (oponent)
Binární matice neobsahující menší matici jako podmatici se stávají zajímavým tématem. V mé práci uvádím dva nové algoritmy pro testování, zda velká čtvercová binární matice obsahuje menší binární matici, a randomizovaný proces, který aproximuje uniformní náhodnou matici neobsahující danou matici. Toto umožní vědeckým pracovníkům testovat jejich hypotézy na náhodných maticích. Proto moje práce také obsahuje efektivní přenositelnou implementaci všech zmíněných algoritmů. Powered by TCPDF (www.tcpdf.org)
|
|
|
Pattern-avoiding permutation classes
Opler, Michal ; Jelínek, Vít (vedoucí práce) ; Klazar, Martin (oponent)
Major index permutace π je součet všech indexů i takových, že πi > πi+1. V této práci zkoumáme distribuci major indexu na permutacích neobsahujích zakázané vzory. Zajímá nás hodnota Mm n (Π), což je počet permutací délky n s major indexem m a množinou zakázaných vzorů Π. Podařilo se nám ukázat, že pro jednoprvkovou množinu Π = {σ} krom okrajových triviálních pří- padů, se hodnoty Mm n (Π) chovají monotónně, nebo-li Mm n (Π) ≤ Mm n+1(Π). Hlavním výsledkem je rozbor asymptotického chování hodnot Mm n (Π) pro n jdoucí k nekonečnu. Ukážeme, že pro každé pevné m, Π a dostatečně velké n jsou hodnoty Mm n (Π) rovny polynomu v proměnné n a navíc jsme schopni určit stupně těchto polynomů pro různé množiny zakázaných vzorů. 1
|
host ::
RSS.